/*
求树的高度
*/
#include <stdio.h>
#include <stdlib.h>

// 定义树节点结构
typedef struct Node 
{
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 创建新节点
Node* createNode(int data) 
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 计算树的高度
int treeHeight(Node* root) 
{
    if (root == NULL) 
    {
        return 0;
    } else {
        int leftHeight = treeHeight(root->left);
        int rightHeight = treeHeight(root->right);

        // 返回左右子树中更高的高度，并加上根节点这一层
        return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
    }
}

int main() 
{
    // 创建一个简单的二叉树
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    // 计算树的高度并输出结果
    int height = treeHeight(root);
    printf("Tree height: %d\n", height);

    return 0;
}